package 简单.其他;

import java.util.Arrays;

/**
 * 给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
 * <p>
 * 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
 * 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
 * <p>
 * 以这种方式修改数组后，返回数组 可能的最大和 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximize-sum-of-array-after-k-negations
 */
public class K次取反后最大化的数组和_1005 {

    public static void main(String[] args) {
        int[] nums = {2, -3, -1, 5, -4};
        System.out.println(largestSumAfterKNegations(nums, 2));
    }

    /**
     * 贪心
     *
     * @param nums
     * @param k
     * @return
     */
    public static int largestSumAfterKNegations(int[] nums, int k) {
        //先排序，将负数最小排在前面，那么反转的时候优先反转
        Arrays.sort(nums);
        int cur = -1;
        for (int i = 0; i < nums.length && i < k; i++) {
            if (nums[i] < 0) {
                nums[i] = nums[i] * -1;
                cur++;
            } else {
                break;
            }
        }
        //数组中的负数全部反转完毕，还有反转的次数，如果是偶数，那么重复反转同一个数达到不变的效果
        //如果是奇数，那么-5 -3 -1 2 5 6    ->  5 3 1 2 5 6
        //负数反转之后有可能变成最小的数，所以取临界值1,2中比较小的数进行反转
        if ((k - 1 - cur) % 2 == 1) {
            if (cur == nums.length - 1) {
                nums[cur] = nums[cur] * -1;
            } else if (cur != -1 && nums[cur] < nums[cur + 1]) {
                nums[cur] = nums[cur] * -1;
            } else {
                nums[cur + 1] = nums[cur + 1] * -1;
            }
        }
        return Arrays.stream(nums).sum();
    }

    //TODO 计数排序？？？

}
